package com.bite;

public class Sort {
    /**
     * 希尔排序
     */
    public static void shellShort(int[] arr){

    }
    public static void main(String[] args) {

    }
    /**
     * 直接插入排序
     * 时间复杂度：
     *  最坏：O(n^2)  例如：5 4 3 2 1
     *  最好：O(n)    例如：1 2 3 4 5
     *  当数据趋于有序，直接插入排序效率更高！
     *  空间复杂度：O(1)
     *  稳定性：稳 定
     */
    public static void insertSort(int[] arr){
        for(int i = 1; i < arr.length; i++){
            int temp = arr[i];
            int j = i - 1;
            for(; j >= 0; j--){
                if(arr[j] > temp){
                    arr[j + 1] = arr[j];
                }else{
                    break;
                }
            }
            arr[j + 1] = temp;
        }
    }

    public static void main1(String[] args) {
        int[] arr = {3,1,4,5,2,7,6};
        insertSort(arr);
        for(int x:arr){
            System.out.print(x + " ");
        }
    }
}
